//2300. 咒语和药水的成功对数
class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions,
                                long long success) {
        vector<int> ret;
        sort(potions.begin(), potions.end());
        for (auto& num : spells) {
            long long target =
                success % num ? success / num + 1 : success / num;
            int left = find(potions, target);
            ret.push_back(potions.size() - left);
        }
        return ret;
    }
    int find(vector<int>& potions, long long target) {
        int left = 0;
        int right = potions.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (potions[mid] >= target)
                right = mid;
            else
                left = mid + 1;
        }
        if (potions[left] < target)
            return potions.size();
        return left;
    }
};

//排序链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return head;

        ListNode* mid = findmid(head);
        ListNode* mid_right = mid->next;
        mid->next = nullptr;

        ListNode* left = sortList(head);
        ListNode* right = sortList(mid_right);
        return mergesort(left, right);
    }
    ListNode* findmid(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    ListNode* mergesort(ListNode* left, ListNode* right) {
        ListNode* new_head = new ListNode(-1);
        ListNode* cur = new_head;
        while (left && right) {
            if (left->val < right->val) {
                cur->next = left;
                cur = cur->next;
                left = left->next;
            } else {
                cur->next = right;
                cur = cur->next;
                right = right->next;
            }
        }
        if (left) {
            cur->next = left;
        }
        if (right) {
            cur->next = right;
        }
        return new_head->next;
    }
};

//LRU 缓存
struct DListNode {
    int key = -1;
    int val = -1;
    DListNode* next = nullptr;
    DListNode* prev = nullptr;
    DListNode() {}
    DListNode(int k, int v) : key(k), val(v) {}
};
class LRUCache {
    DListNode* head;
    unordered_map<int, DListNode*> m;
    int size;

public:
    LRUCache(int capacity) : size(capacity) {
        head = new DListNode();
        head->next = head;
        head->prev = head;
    }

    int get(int key) {
        if (m.count(key)) {
            DListNode* t = m[key];
            DListNode* prev = t->prev;
            DListNode* next = t->next;
            prev->next = next;
            next->prev = prev;
            addtohead(t);
            return t->val;
        } else
            return -1;
    }

    void put(int key, int value) {
        if (m.count(key)) {
            DListNode* t = m[key];
            DListNode* prev = t->prev;
            DListNode* next = t->next;
            prev->next = next;
            next->prev = prev;
            addtohead(t);
            t->val = value;
            return;
        } else {
            DListNode* new_key = new DListNode(key, value);
            addtohead(new_key);
            m[key] = new_key;
        }
        if (m.size() > size) {
            DListNode* end = head->prev;
            DListNode* prev = end->prev;
            DListNode* next = end->next;
            m.erase(end->key);
            delete end;

            prev->next = next;
            next->prev = prev;
        }
        return;
    }
    void addtohead(DListNode* new_key) {
        DListNode* next = head->next;
        new_key->prev = head;
        new_key->next = next;

        head->next = new_key;
        next->prev = new_key;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */